// https://leetcode.cn/problems/sort-colors/description/

// 算法思路总结：
// 1. 三指针（荷兰国旗）算法原地排序三种颜色
// 2. l指向0的右边界，r指向2的左边界，cur遍历指针
// 3. 遇到0：与l+1交换，cur++；遇到1：cur++；遇到2：与r-1交换
// 4. 循环条件：cur < r（确保2区域不被重复处理）
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    void sortColors(vector<int>& nums) 
    {
        int m = nums.size();

        for (int l = -1, r = m, cur = 0 ; cur < r ; )
        {
            if (nums[cur] == 0)
            {
                swap(nums[++l], nums[cur++]);
            }
            else if (nums[cur] == 1)
            {
                cur++;
            }
            else if (nums[cur] == 2)
            {
                swap(nums[--r], nums[cur]);
            }
        }

        return ;
    }
};

int main()
{
    vector<int> nums1 = {2,0,2,1,1,0}, nums2 = {2,0,1};
    Solution sol;

    sol.sortColors(nums1);
    sol.sortColors(nums2);

    for (const int& num : nums1)
        cout << num << " ";
    cout << endl;

    for (const int& num : nums2)
        cout << num << " ";
    cout << endl;

    return 0;
}